(navigation image)
Home American Libraries | Canadian Libraries | Universal Library | Community Texts | Project Gutenberg | Children's Library | Biodiversity Heritage Library | Additional Collections
Search: Advanced Search
Anonymous User (login or join us)
Upload
See other formats

Full text of "Evolutionary Algorithmical Approach for VLSI Physical Design- Placement Problem"

ACEEE Int. J. on Electrical and Power Engineering, Vol. 02, No. 02, August 201 1 



Evolutionary Algorithmical Approach for VLSI 
Physical Design- Placement Problem 

Varatharajan .R ', Perumal Sankar.S 2 , Lekha.R 3 , Kumar avel 4 

1 Bharath University,Department of ECE,Chennai,India 

E-mail :varathu21 @ !yahoo.com 

2 Cape Institute of Technology,Department of ECE,Kanyakumari, India 

E-mail: spsankar2004 @ yahoo, co. in 

3 Bharath UniversityDepartment of ECE,Chennai,India 

E-mail:lekhavathy@gmail.com 

4 Bharath UniversityDepartment of CSC,Chennai,India 

E-mail :drkumaravel @ gmail. com 



Abstract:-Phjsical layout automation is very important in 
VLSI's field. With the advancement of semiconductor 
technology, VLSI is coming to VDSM (Very Deep Sub 
Micrometer), and the scale of the random logic IC circuits 
goes towards million gates. Physical design is the process of 
determining the physical location of active devices and 
interconnecting them inside the boundary of the VLSI 
chip.The earliest and the most critical stage in VLSI layout 
design is the placement. The background is the rectangle 
packing problem: given a set of rectangular modules of 
arbitrary sizes, place them without overlap on a plane within 
a rectangle of minimum area [1], [5]. The VLSI placement 
problem is to place the object in the fixed area of die without 
overlap and with some cost constrain such as the wire length 
and area of the die. The wire length and the area optimization 
is the major task in the physical design. We first 
introduce about the major technique involved in the algorithm. 

Index Terms: Placement problems, Memetic algorithm, wire 
length minimization, area minimization. 

I .Introduction 

The task of the very large scale integration (VLSI) 
placement is to assign exact location to various circuit 
components within the chip area. It involves number of 
objectives such as wire length, area of the die, timing and 
power. Placement treats the shapes of all blocks as fixed, i.e., 
it only determines the location of each block on the chip. The 
variables are the xy locations of the blocks; most blocks are 
standard cells. The y-locations of cells are restricted to 
standard- cell rows. Placement instance sizes range in to the 
tens of millions and will continue to increase. Placement is 
usually divided into two steps: global placement and detailed 
placement [1]. Global placement assigns blocks to certain 
sub regions of the chip with out determining the exact location 
of each component within its sub region. As a result, the 
blocks may still overlap. Detailed placement starts from the 
result of global placement, removes all overlap between 
blocks, and further optimizes the design. Placement objectives 
include the estimated total wire length needed to connect 
blocks in nets, the maximum expected wiring congestion in 
subsequent routing and the timing performances of the 
circuit. To solve such large scale mixed size VLSI placement 
problem many algorithms are used in VLSI. Among these 
algorithms memetic algorithm is used to solve the placement 

©2011 ACEEE 
DOI:01.DEPE02.02.3 



problem considered here. The placement algorithms are 
classified into constructive and iterative improvement methods 
[3]. The constructive algorithm starts with the empty set and 
builds up the partition by adding one element at a time. These 
algorithms are faster but the quality of result is not good. An 
iterative algorithm starts with initial placements and repeatedly 
modifies it. These algorithms give good result but takes long 
time. The placement problems are the wire length [2] and area 
of the die [3], routability, power minimization and delay [2]. 
Out of these above mentioned problems the area minimization 
and the wire length minimization are the most critical part. For 
the area and wire length optimization a modern placer needs 
to handle the large-scale design with millions of objects, 
heterogeneous objects with different sizes and various 
constrained placement such as preplaced blocks and chip 
density. The traditional approach in placement is to construct 
an initial solution by using constructive heuristic algorithms. 
A final solution is then produced by using iterative 
improvement techniques where a modification is usually 
accepted if a reduction in cost occurs, otherwise it is rejected. 
The solution generated by constructive algorithms may be 
far from optimal. Thus an iterative improvement algorithm is 
performed next to improve the solution and the computation 
time of such algorithm is also large. For many combinatorial 
optimization problems, no effective algorithms capable of 
finding guaranteed optimum solutions in short time are 
available. Therefore, powerful heuristics have been developed 
that deliver the guarantee optimum solution, but have shown 
to be highly effective in many test cases. A special class of 
heuristics is investigated. The algorithms under consideration 
are called memetic algorithms, which are - roughly speaking - 
hybrids of evolutionary algorithms and problem-specific 
search algorithms, such as greedy heuristics and local search. 
Memetic algorithms (MAs) are evolutionary algorithms (EAs) 
that apply the local search process to refine the individual 
MAs include a broad of metaheuristics [5] ,[4]. This method is 
based on the population of agents and proved to be of practical 
success in a variety of problem domains. We can be sure that 
MAs constitute one of the most successful approaches for 
combinatorial optimization in general and for the approximate 
solution of NP optimization problems. The reminder of this 
paper is organized as follows: section 2 gives the memetic 
algorithm flow, Section 3 involves the equation in the 



^ACEEE 



ACEEE Int. J. on Electrical and Power Engineering, Vol. 02, No. 02, August 201 1 



placement problem and Section 4 shows the experiment result 
for the problem considered. 

II. Memetic Algorithms 

Memetic Algorithms are class of stochastic global search 
heuristics in which Evolutionary Algorithm based approaches 
are combined with problem-specific solvers. Later local search 
heuristics techniques are implemented. This hybridisation is 
to either accelerate or to discover good solution from the 
population where the evolution alone would take long time 
to discover or to reach the solution. Memetic Algorithms use 
heuristic local searches either approximate method or exact 
method to get the local refined solution from the population. 
There are several reasons for hybridising evolutionary 
algorithms with local searchers. Some of them are mentioned 
below: 

1. Complex problems are decomposed to different sub 
problems could be better solved by different methods. 

2. The hybridisation of evolutionary algorithm with local 
search algorithm result in fine tuning or repairing the best 
solution(s) produced by the evolutionary algorithm. The 
powerful local searcher introduces diversity into the solution. 

3. The sub problems are dealt by the various operators, 
for example cross over and mutation or by the local searcher. 
Thus the search process is done with in the search space 
region. 

4. In some cases the available exact or approximate 
methods for the sub problems are included with the 
evolutionary algorithm. 

5. The heuristic or local search is used to repair the 
solutions found by the evolutionary algorithm. The heuristic 
or local search do the same in the Memetic algorithm. Such 
heuristic are called Meteheuristic algorithm. 

A. Memetic algorithm flow 

Memetic algorithms try to simulate cultural evolution 
rather than the biological one, as evolutionary algorithm do. 
They are a combination of population based global 
optimization and heuristic local search. First individuals are 
initialized randomly. Starting with each single individual, one 
local search is performed. After that, the individuals start to 
interact either competitively (in selection form) or by 
cooperatively (in recombination form). These two steps are 
repeated until the stopping criterion is met. From this context 
of above we can know that memetic algorithm acts as two 
level optimization algorithm, the top level algorithm is an 
evolutionary algorithm otherwise a population based 
algorithm and at the bottom levels a single individual 
optimizer like hill climbing or simulated annealing or some 
other local search algorithm. 

B. Evolutionary Algorithms + Local Search = Memetic 
Algorithms 

Combining global and local search algorithm used for 
many hybrid optimization approaches. Memetic algorithms 
(MAs) are Evolutionary Algorithms (EAs) and along with 
that we apply some sort of local search algorithm to further 
improve the fitness of individual in the population. Memetic 

©2011 ACEEE 
DOI:01.LTEPE02.02.3 



Algorithms have been shown to be very effective in solving 
many hard combinatorial optimization problems. The 
approach combines a hierarchical design technique, Genetic 
Algorithms, constructive algorithms and advance local search 
to solve the VLSI layout in various steps like partitioning 
and placement. The efficient optimization algorithm used to 
solve hard problems usually employs a hybrid of at least two 
techniques to find a near optimal solution to problem 
considered. The main motivation for this hybridisation is to 
increase the efficiency that is to get the good quality solution 
in specified time. 




Initial population 




I 




Mating pool 



T 




Selection 



t 



Cross over 




f 



Offspring 




Mutation 




Offspring 




Figure 1 . Algorithm Template 

The above figure identifies the Memetic algorithm 
template. The structure is the basic evolutionary algorithm 
structure and the black mark placed on the particular block is 
to mention that hybridisation takes place in that block. Each 
of the black mark provides an opportunity for hybridisation. 
For example the initial population could be seed with 
solutions arising from sophisticated problem for specific 
heuristics. The cross over and mutation operator could be 
enhanced with domain specific and representation specific 
constrain as to provide better search ability to Evolutionary 
Algorithm. More over local search could be applied to any or 
all of the intermediate set of solution, for example, offspring 
set. The more problem specific knowledge is incorporated 
with in a Memetic algorithm the better it will perform. The 
most popular form of hybridisations is to apply one or more 
phase of local search, based on some probability parameter, 
to individual members of population in each generation. 

C. Memetic Algorithm for Circuit Placement 

The placement is nothing but arranging the circuit 
components in layout. In general-cell and standard-cell 



^cACEEE 



ACEEE Int. J. on Electrical and Power Engineering, Vol. 02, No. 02, August 201 1 



placement, we have to position the components of the circuit 
such that the layout area is minimized. The area measure 
used here comprises the area taken up by the circuit 
components as well as the area needed for wiring the circuit 
components. The placement problem has the dual flavour of 
a two dimensional packing problem and connection cost 
optimization problem. The packing problem is concerned 
with fitting a number of cells of different sizes and shapes 
tightly into a rectangle. The connection cost optimization 
aims at minimizing the amount of wire that is needed. The 
proposed Memetic Algorithm for circuit placement [4] [5] is 
based on the Genetic Algorithm . In each generation, a Tile- 
based local search heuristic is performed on part of the 
population to improve their fitness. The local search maybe 
introduced in genetic algorithm to offspring population, it 
may be in cross over or else where. For the circuit placement 
problem, the pure Genetic Algorithm is combined with Tile- 
based local search in three different ways, referred to as 
performing local search on part of the population: (i) before 
the crossover (ii)after the crossover (iii) before and after the 
crossover. [1]. 

1. Encode solution space for placement 

2. Set population size, max-gen, generation=0; 
Set crossover-rate, mutation-rate; 

3. Generate the initial population 

4. Evaluate the initial population 

5. While (generation < max-gen) 

Apply genetic algorithm 

Apply tile-based local search to population 
End while 

6. Return the best solution in current population 

Figure 2. Pseudocode for Memetic placement algorithm 

A Memetic algorithm for the circuit placement is purely 
based on the Genetic algorithm. From the above figure we can 
under stand that the memetic algorithm for the circuit place- 
ment starts with the initial random population generation 
before that we have to set the size of the population , maxi- 
mum number of generation, cross over rate, and mutation rate. 
Next we apply the Genetic algorithm, the genetic algorithm 
start with the selection process, the selection process is based 
on the fitness function. The chromosome for the cross over is 
selected using this fitness function . Cross over is the base 
point for the next generation population. The cross over tech- 
nique used in Genetic algorithm is one point cross over, two 
point cross over, cut and splice cross over , uniform cross 
over and half uniform cross over. After the cross over, the 
mutation process is done to maintain the genetic diversity 
from one generation to next generation. In this mutation the 
genetic sequence will be changed from its original by gener- 
ating a random variable for each bit sequence. After the muta- 
tion, accepting offspring is placed in the new population for 
further iteration. The next step in memetic algorithm for cir- 
cuit placement is to apply the local search algorithm in be- 
tween this genetic algorithm. As mentioned before the local 
search is applied in three ways as given below: 
(i) Before the crossover 
(ii) After the crossover 



(iii) Before and after the crossover. 

III. Placement Problem Description 

A. Area Estimation 

Given a set of module M„ 1VL, M and set of n 

1' 2' n 

interconnects N ,N, N the objective of the placement is 

to obtain the non overlapping package of all the modules 
which achieves some optimization objective such as 
minimizing the area of package[3], the interconnection length 
as shown in the figure below: 

^ J 












2 


4 










1 


5 




3 





H 



Figure 3. Six block placement 

B. Horizontal Constrain: 

If (-X,Y) =(. . . a. . .b . .,a. . . b. . .) Block b is is at right side 
of the block a 

C. Vertical Constrain: 

If (X,Y)=(. . . a. . .b. . .,b.. . a. . .) Block b is at the below 
side of the block a Based on "left of constraint of (X, Y), a 
directed and vertex-weighted graph G H (V, E) (V: vertex set, E: 
edge set), called the horizontal-constraint graph (HCG) is 
constructed as follows: 

£1) V= {S h } TJ {t h } U {bj H i = 1 = . . . , M}, 

Where b correspond to the block 

S h is the source node representing the left boundary 
L is the target node representing the right boundary 

(2) E = {(S t: bi) i| = 1 , . . . M] U {(b i: ti) | i = 1 : . . . >!} U 
«Kb|) ...K..^} 

If existing, edge (b.,b. +1 ) edge (b. +1 ,b. +2 ) and edge (b.,b. +2 ) 
then (b.,b. ,) omitted 

3) Vertex Weight equals the width of the block b but zero for 
S h and t. similarly the vertical constrain graph (VGH) as show 
in the below figure. Vertical constrain graph G (V,E) is 
constructed using "above" constrain and the height of the 
each block. As for the example show in the above figure. The 
corresponding constrain graph G h (V,E) and G v (V,E) are as 
show in the figures. Both G h (V,E) and G v (V,E) are vertex 
weighted acyclic graph so longest path algorithm can be 
applied to find the x and y co ordinates of each block. 



©2011 ACEEE 
DOI:01.LTEPE02.02.3 



^ACEEE 



ACEEE Int. J. on Electrical and Power Engineering, Vol. 02, No. 02, August 201 1 




Figure 4. Example for vertical constrain graph (VGH) 

The coordinates of the block coordinate of the lower left 
corner of the block. 




Figure 5. Example for horizontal constrain graph 

D. Wire length estimation. 

We are addressing the problem of VLSI standard Cell 
placement with the objectives of minimizing wire length [2], 
power consumption, and timing performance (delay), while 
considering the layout width as a constraint. 

E. Wire length measurement and Cost: 

In VLSI placement the cells present in the module are 
connected by wire. The estimation of wire length [2] required 
for connection is calculated by the formula 

Wire lcngth ="w ij ((x i -x/ + (y i -y/) 

I>j 

Where 
w . weight of the connection between cell x and y 

(x - x ) distance in X direction 

v i / 

(y - y ) distance in Y direction 
Inter connect wire length of each net in the circuit is estimate 
during Steiner tree and then total wire length is computed by 
adding the individual estimates 

©2011 ACEEE 
DOI:01.DEPE02.02.3 



Cost ="1 

wire l 

i€M 
Where 1 is the wire length estimation for net i and M denotes 
total number of nets in circuit. 

IV Experimental Result 

The Memetic algorithm for VLSI cell placement problem 
was tested on real life circuits chosen from a benchmark suite 
that for design work shop in early 1990's and it is often referring 
to as MCNC benchmark. They were originally released and 
maintained by North Carolina's Microelectronics, computing 
and networking centre and now it got changed to CAD 
Benchmarking Laboratory (CBL). All results of our Memetic 
algorithm presented in this section were obtained by 
implementation of Memetic algorithm for placement. Here 
first the initial population is generated and the fitness function 
is evaluated. Based on that fitness selection of parents for 
the cross over. After this process the normal mutation and 
inversion operation takes place, in addition to this process 
for each sub population, the local search is applied to refine 
the fitness of each individual to get the most optimal 
solution.We are implementing our algorithm in c language as 
(genetic algorithm + local search) , and the experiment is 
executed on the Intel Pentium processor (3. 1GHz, 5 12 RAM) 
machine running windows xp . The memetic algorithm (genetic 
algorithm + local search) is embedded in our algorithm the 
block placement. The results obtained by implementing our 
algorithm are shown in the table below: 

Table 1 .Performance statistics for MCNC Benchmark circuits 



Psicmimce statistics for ftvsMCXC Benchmark circuits 


Circuit 


Cells 


\"ets 


Final iiire 
length(mm) 


Final chip are: 
(mm") 


aj;t; 


9 


97 


590.6 


61J 


xerox 


10 


203 


103 S 


32.6 


hp 


11 


33 


365 


42.9 


Ami33 


33 


123 


27S.5 


1.23 


Ami49 


49 


-::§ 


2077 






V. Conclusions 

The hybrid approach for the combinatorial placement 
problem is memetic algorithm, this memetic algorithm may 
also be called as hybrid genetic algorithm, here the 
hybridisation is done in genetic algorithm with some local 
search technique. First the memetic algorithm starts with the 
genetic algorithm, finds the global minimum solution and to 
further refine the individual and to get the local minimum we 
introduce a local search. The main future of the approach 
introduced here, in comparison with other approaches, is the 
manner in which block flexibility is treated. During the 
iteration several implementation such as wire length 
calculation and area estimation are considered and some 
shape functions are introduced for the block. The common 
hill climbers in genetic algorithm for combinatorial optimization 
problem randomly explore the solutions neighbouring the 
candidate solution encoded in the current individual and 
accept those with better fitness. In hybrid approaches, local 
search techniques explore the solution space close to the 
sample points by applying specialized heuristics. When 



-^cACEEE 



ACEEE Int. J. on Electrical and Power Engineering, Vol. 02, No. 02, August 201 1 



including problem specific knowledge during creation of 
individual, as in our approach, it is possible to identify 
unfavourable or redundant partial solutions and consider 
only the most promising ones. Therefore, each individual in 
our hybrid genetic algorithms encodes a set of high quality 
solutions, the best of which is a local optimum. This paper 
explores the memetic algorithm strategies for a multi objective 
VLSI cell placement. The results produced by implementing 
memetic algorithms are the most optimal solution compared 
to other set of algorithm used for VLSI cell placement. In this 
paper wire length estimation and area estimation were 
considered. For future work: width cost, delay cost, power 
cost and power minimization are the parameters that can be 
considered. 

Acknowledgment 

It is to note here that this topic-specific article for the 
easy reference of VLSI Placement Problem, optionally being 
used together with the all the problems in VLSI 
PhysicalDesign. Author Varatharajan, I thank the management 
of Bharath University, India to conduct his research in this 
area and also he worked under the Guidance of Dr.Perumal 
sankar and Dr.Kumaravel , the Eminent Professors in India. 
He thank the guide for his moral support to continue the 
research. 



References 

[ 1 ] Chen 1 , and Yao-WenChang 1 ' 2 Tung-Chieh Chen2, Jiang 1 , Hsin- 
Chen Zhe-Wei; "challenges and solution in modern VLSI placement" 
2007 IEEE 1-4244-0583-1/07. 

[2] Sadiq M. Sait, Mustafa Imran Ali, and Ali Mustafa Zaidi; 
"Evaluating Parallel Simulated Evolution Strategies for VLSI Cell 
Placement" in 1-4244-0054-6/06 ©2006 IEEE. 
[3] Ning Xu,Feng Huang ,Zhonghua Jiang ; "A Fast Algorithm for 
VLSI Building Block Placement" in MACS Multiconference on 
"Computational Engineering in Systems Applications" (CESA), 
October 4-6, 2006, Beijing, China.pp230-239. 
[4] Natalio Rrasnogor, and Jim Smith; "A Tutorial for Competent 
Memetic Algorithms: Model, Taxonomy and Design issues" IEEE 
Transactionson Evolutionary Computation, Vol. A, No.B, 
CCC200D. 

[5] Bo Hu and Malgorzata Marek-Sadowska, "Multi level Fixed- 
Point-Addition-Based VLSI Placement" IEEE Transactionson 
Computer Aided Design Of Integrated Circuits And Systems, Vol.24, 
No.8, August2005. 



©2011 ACEEE 
DOr.Ol.DEPE.02.02.3 



10 



^ACEEE